First Course in Algorithms Through Puzzles by Ryuhei Uehara

Author:Ryuhei Uehara
Language: eng
Format: epub, pdf
ISBN: 9789811331886
Publisher: Springer Singapore

Exercise 27

Describe the points to which you should pay attention when you implement the merge sort method as a stable sort.

Analysis of quick sort. In the practical sense, quick sort is quite a fast algorithm and, in fact, is used in real systems. However, since quick sort has some special properties when it is applied, we have to understand its behavior.

The space complexity of quick sort is easy to determine. It requires a few variables, but large additional memories are not needed if we swap data in the array itself (we sometimes call this method “in place”). Therefore, excluding the input array, the space complexity is O(1). In general, the quick sort method is not stable. (For example, in the partition procedure described in this book, it finally swaps the pivot and . In this case, when , their ordering is swapped and the resulting array is no longer stable.)

Then, how about time complexity? In the quick sort method, the algorithm first chooses the pivot and then divides the array into two parts by comparing the data items to this pivot. The running time depends on the size of these two parts. Therefore, the dexterity of this choice of pivot is the key point for determining the time complexity of the quick sort method. We consider this part step by step.

Ideal case. When does the algorithm run ideally, or as fast as it can? The answer is “when the pivot is always the median in the array.” In this case, the array is divided into two parts of the same size. Then, we can use the same analysis as we used for merge sort, and the number of levels of recursive calls is . The point in which it differs from the merge sort algorithm is that quick sort does not need to merge two subarrays after recursive calls. When the algorithm proceeds to the last case after repeating the procedure of dividing by pivots, it does not merge the subarrays. Therefore, it is sufficient to consider the cost of the partition of the array. When we consider its time complexity from the viewpoint of the algorithm, it is not so easy to analyze it. However, as in the case of merge sort, it is easy from the viewpoint of the data in the array. Each element in the current subarray is compared to the pivot exactly once, and swapped if necessary. Therefore, the time complexity of the division of an array of size is . Thus, the total time complexity is , the same as that of merge sort.

Worst case. Now, we consider the worst case for the quick sort algorithm. This case occurs when the algorithm fails to choose the pivot correctly. Specifically, the selected pivot is the maximum or minimum value in the array. Then, this “division” fails, and the algorithm obtains one array of size 1 that contains only the pivot and another array that contains all the remaining elements. We consider the time complexity of this worst case.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.